package com.beautiful.xin.other;

/**
 * @author xuqingxin 2021/7/25 10:36 上午
 */
public class FibonacciTest {
    public static void main(String[] args) {

        int n = 10;
        for (int i = 0; i < n; i++) {
            System.out.println(fibonacciRecur(i));
        }

        System.out.println("==========");
        for (int i = 0; i < n; i++) {
            System.out.println(fibonacciNonRecur(i));
        }
    }

    private static int fibonacciNonRecur(int n) {
        if (n == 0 || n == 1) {
            return n;
        }

        int[] in = new int[n + 1];

        in[0] = 0;
        in[1] = 1;
        for (int i = 2; i <= n; i++) {
            in[i] = in[i - 1] + in[i - 2];
        }
        return in[n];
    }

    private static int fibonacciRecur(int n) {

        if (n == 0 || n == 1) {
            return n;
        }
        return fibonacciRecur(n - 1) + fibonacciRecur(n - 2);
    }
}
